КОМБИНАТОРИКА ЭЛЕМЕНТТЕРІ

Материалды дайындағандар

жоғары математика кафедрасының доценті Ж. Рахметуллина

Комбинаторика – берілген жиынның элементтері арқылы белгілі бір құрастырулар шарттарына бағынатын, барлық мүмкін болатын топтастырулар(нұсқалар) саны зерттелетін математиканың бөлімі.

Нақты бір қасиеттерге ие болатын топтастырулар санын табу үшін оларды анықтап, сонан кейін санау керек. Топтастырулар санын арнайы формулалар бойынша немесе комбинаториканың негізгі ережелері бойынша, топтастырулар түрін көрсетпей есептеуге болады.

Қосынды ережесі. Егер бірінші типті элементті тәсілмен, ал екінші типті элементті тәсілмен және s-ші типті элементті тәсілмен алуға болса, онда бір элементті әдіспен алуға болады.

Көбейтінді ережесі. Егер бірінші типті элементті тәсілмен, ал екінші типті элементті тәсілмен және s-ші типті элементті тәсілмен алуға болса, әр типтен бір-бір элементтен әдіспен алуға болады.

Мысал 1. Қапта 6 алмұрт, 4 алма, 3 киви және 7 мандарин бар болсын. Бір жемісті қанша тәсілмен алуға болады?

Қосынды ережесі бойынша: 6 + 4 + 3 + 7 = 20 тәсілмен.

Мысал 2. Оқушы каникулға тапсырма алды: алты теореманың кез-келген біреуінің дәлелдеуін жаттау, жеті романның біреуін оқу, төрт тақырыптың біреуіне шығарма жазу. Берілген тапсырманы қанша тәсілмен орындауға болады?

Көбейтінді ережесі бойынша: тәсілмен.

Комбинаториканың кейбір ұғымдарын және нәтижелерін қарастырайық: k элементтен жиынтық k көлемді таңдама деп аталады. Мәселен, элементтерінің құрамы бірдей, ал олардың орналасу реті өзгеше болған таңдамаларды айыруға (реттелген таңдама), немесе айырмауға (реттелмеген таңдама) болады.

Таңдамадағы элементтер қанша қажетті сонша рет қайталанатын болса, яғни, алынған элемент қайтарылып, қайтадан алынса, онда мұндай таңдамалар қайталаумен (немесе қайтарылған) деп аталады. Егер таңдамада әрбір элемент тек қана бір рет кездесетін болса, онда мұндай таңдамалар қайталаусыз (немесе қайтарылусыз) деп аталады.

Келесі ұғымдарға тоқталайық:

- қайталаусыз реттелген таңдамалар саны немесе n элементтен k элемент бойынша қайталаусыз алынған орналастырулар саны;

- қайталаумен реттелген таңдамалар саны немесе n элементтен k элемент бойынша қайталаумен алынған орналастырулар саны;

- қайталаусыз реттелмеген таңдамалар саны немесе n элементтен k элемент бойынша қайталаусыз алынған терулер саны;

- қайталаумен реттелмеген таңдамалар саны немесе n элементтен k элемент бойынша қайталаумен алынған терулер саны;

- элементтерінің орналасу реті ғана өзгеше болған n элементтен қайталаусыз алынған алмастырулар саны;

- элементтерінің орналасу реті ғана өзгеше болған элементтерден құрамында бірінші типті элемент, ал екінші типті элемент және т.с.с. қайталаумен алынған алмастырулар саны.

Мысал 3. Алты қабатты үйдің лифтісіне бірінші қабатта үш жүргінші кірді. Егер жүргіншілердің әр қабатта шыққаны белгілі болса, онда барлығы қанша жағдай болуы мүмкін?

Қайталаусыз реттелген таңдамалар саны немесе 5 элементтен 3 элемент бойынша қайталаусыз алынған орналастырулар саны: .

Мысал 4. Автоматты сақтау камерасында 0, 1, ..., 9 цифрларымен төрт диск бар. Сақтау камерасындағы шифр - 10 цифрдан көлемі 4-ке тең таңдама. Шифрдағы цифрлардың орналасу реті өзгеше және қайталанған болуы мүмкін. Ендеше, қайталаумен реттелген таңдамалар, ал олардың барлық саны тең.

Мысал 5. Қапта 18 шар бар. Олардың ішінде: 4 қызыл, 6 көк және 8 сары. Қаптан 1уі қызыл, 1уі көк және 2уі сары болатындай 4 шарды қанша тәсілмен алуға болады?

Ендеше, есеп қайталаусыз теру жайында. Онда қаптан құрамында 1уі қызыл, 1уі көк және 2уі сары болатындай 4 шарды алудың тәсілдер саны:

.

Мысал 6. Дүкенде раушангүлдердің үш сұрыпы бар. Бес гүлді жинақты қанша тәсілмен алуға болады?

Есеп шартына сәйкес, қайталаумен теру формуласын қолдансақ, онда

.

Мысал 7. о, п, р, с, т әріптерін ауыстыра отырып, 5 әріптен тұратын қанша «сөз» алуға болады?

Тек қана орналасу ретімен өзгешеленетін әріптердің орындарын ауыстырып алынған реттелген қайталаусыз алмастырулар саны:.

Мысал 8. Картон қағаздарға «МИССИСИПИ» сөзін құрайтын әріптер жазылған. Кішкентай бала картон қағаздарын араластырып,, бір қатарға қояды. Ол әр түрлі қанша «сөз» құрастыра алады?

Сынақтың нәтижесі - картон қағаздарын орналастыру: Әріптер арасында қайталанатыны кездесетін болғандықтан, реттелген қайталаумен алмастырулар саны: .

Ескерту: Таңдама түрін төмендегі блок сұлбасымен анықтаған тиімді: